/**
 * 
 */
package tree.passed;

/**
 * @author xyyi
 *
 */
public class ConvertSortedArrayToBinarySearchTree {

	/**
	 * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
	 */
	public TreeNode sortedArrayToBST(int[] num) {
		return sortedArrayToBST(num, 0, num.length - 1);
	}

	public TreeNode sortedArrayToBST(int[] num, int begin, int end) {
		if (begin > end)
			return null;
		if (begin == end)
			return new TreeNode(num[begin]);

		int mid = begin + (end - begin) / 2;
		TreeNode node = new TreeNode(num[mid]);
		node.left = sortedArrayToBST(num, begin, mid - 1);
		node.right = sortedArrayToBST(num, mid + 1, end);
		return node;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public ConvertSortedArrayToBinarySearchTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
